package month1;

public class SortList148_04 {
    public static void main(String[] args) {
        System.out.println(mergeSort(new ListNode(new int[]{6, 5, 3, 2, 4, 1})));
    }

    /**
     * 归并排序
     * @param head
     * @return
     */
    static ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    static ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode s = head, f = head.next;
        while(f != null && f.next != null) {
            f = f.next.next;
            s = s.next;
        }
        f = s.next;
        s.next = null;
        ListNode l = mergeSort(head), r = mergeSort(f);
        ListNode dummy = new ListNode();
        ListNode tmp = dummy;
        while(l != null || r != null) {
            int l1 = l == null ? Integer.MAX_VALUE : l.val, l2 = r == null ?  Integer.MAX_VALUE : r.val;
            if (l1 < l2) {
                tmp.next = new ListNode(l1);
                l = l.next;
            } else {
                tmp.next = new ListNode(l2);
                r = r.next;
            }
            tmp = tmp.next;
        }
        return dummy.next;
    }
}
